1. Technical Field
This invention relates generally to providing directory services in a distributed computing environment.
2. Description of the Related Art
A directory service is the central point where network services, security services and applications can inform other entities in the network about their services, thus forming an integrated distributed computing environment. The current use of directory services may be classified into several categories. A "naming service" (e.g., DNS and DCE Cell Directory Service (CDS)) uses a directory as a source to locate an Internet host address or the location of a given server. A "user registry" (e.g., Novell NDS) stores information of all users in a system composed of a number of interconnected machines. The central repository of user information enables a system administrator to administer the distributed system as a single system image. Still another directory service is a "yellow pages" lookup provided by some e-mail clients (e.g., Netscape Communicator, Lotus Notes, Endora and the like).
With more and more applications and system services demanding a central information repository, the next generation directory service will need to provide system administrators with a data repository that can significantly ease administrative burdens. In addition, the future directory service must also provide end users with a rich information data warehouse that allows them to access department or company employee data, as well as resource information, such as name and location of printers, copy machines, and other environment resources. In the Internet/intranet environment, it will be required to provide user access to such information in a secure manner.
To this end, the Lightweight Directory Access Protocol (LDAP) has emerged as an Internet Engineering Task Force (IETF) open standard to provide directory services to applications ranging from e-mail systems to distributed system management tools. LDAP is an evolving protocol that is based on a client-server model in which a client makes a TCP/IP connection to an LDAP server, sends requests, and receives responses. The LDAP information model, in particular, is based on an "entry", which contains information about some object. Entries are typically organized in a specified tree structure, and each entry is composed of attributes.
LDAP provides the capability for directory information to be queried or updated. It offers a rich set of searching capabilities with which users can put together complex queries to get desired information from a backing store. As originally implemented (at the University of Michigan), LDAP used several freely available b-tree packages, such as the GNU dbm and Berkeley db44 packages. This reference implementation, however, does not provide a reliable and scaleable enterprise directory, in part, because of the use of a btree-based backing store.
One problem is that different vendors provide different mechanisms for the tree structure. For example, DB/2 provides the WITH clause in a Structured Query Language (SQL) SELECT statement to provide subtree transversal with arbitrary depth. Oracle, however, used CONNECT BY PRIOR and START WITH clauses in the SELECT statement to provide partial support for reachability and path enumeration. Other database management systems used different SQL semantics. In any case, all such mechanisms end up using recursive queries to handle hierarchical structures such LDAP entries. Recursive queries do not scale up well as the number of records in a relation table increases. Indeed, in a simple example involving 1000 LDAP entries, using DB/2 recursive queries, a simple SELECT takes more than several minutes to complete.
Thus, there is a need to provide a faster and more efficient method to support LDAP searches with relational tables without the overhead of recursive queries. This invention addresses and solves this problem.